package com.github.kezhenxu94.playground.java.atoffer;

/**
 * 二维数组中的查找
 *
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，
 * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 
 */
public class AtOfferTwoDimentionArraySearch {

	public static void main(String[] args) {
		int[][] array = new int[0][0];
		AtOfferTwoDimentionArraySearch sol = new AtOfferTwoDimentionArraySearch();
		System.out.println(sol.find(array, 16));
	}

	public boolean find(int[][] array, int target) {
		if (array.length == 0 || array[0].length == 0)
			return false;
		return findHelper(array, 0, array.length - 1, target);
	}

	private boolean findHelper(int[][] array, int firstRow, int lastColumn, int target) {
		if (firstRow == array.length - 1 || lastColumn == 0)
			return array[firstRow][lastColumn] == target;
		if (array[firstRow][lastColumn] < target)
			return findHelper(array, firstRow + 1, lastColumn, target);
		if (array[firstRow][lastColumn] > target)
			return findHelper(array, firstRow, lastColumn - 1, target);
		return true;
	}
}
